# 贪婪解法
# class Solution(object):
#     def wordsTyping(self, sentence, rows, cols):
#         """
#         :type sentence: List[str]
#         :type rows: int
#         :type cols: int
#         :rtype: int
#         """
#         n = len(sentence)
#         index = 0
#         for _ in range(rows):
#             j = 0
#             while j + len(sentence[index % n]) <= cols:
#                 j += (len(sentence[index % n]) + 1)
#                 index += 1
#         return index // n

import collections
class Solution(object):
    def wordsTyping(self, sentence, rows, cols):
        """
        :type sentence: List[str]
        :type rows: int
        :type cols: int
        :rtype: int
        """
        n = len(sentence)
        prefix = [0] * n
        prefix[0] = len(sentence[0]) + 1
        for i in range(1, n):
            prefix[i] += (len(sentence[i]) + 1 + prefix[i - 1])
        index = 0
        now_stack = collections.deque()
        for i in range(rows):
            if index == 0 and i != 0:
                break
            if index == 0:
                now_cols = cols
                base = 0
            else:
                if prefix[-1] - prefix[index - 1] <= cols + 1:
                    base = 1
                    now_cols = cols - (prefix[-1] - prefix[index - 1])
                    index = 0
                else:
                    k = index
                    base = 0
                    while prefix[k] - prefix[index - 1] <= cols + 1:
                        k += 1
                    index = k
                    now_cols = 0
            if now_cols > 0:
                base += (now_cols + 1) // prefix[-1]
                now_cols = (now_cols + 1) % prefix[-1]
                while prefix[index] <= now_cols:
                    index += 1
            now_stack.append(base)
        if len(now_stack) == rows:
            return sum(now_stack)
        else:
            total = 0
            epoch = rows // len(now_stack)
            total += epoch * sum(now_stack)
            left = rows % len(now_stack)
            for k in range(left):
                total += now_stack[k]
            return total



data = Solution()
sentence = ["hello", "world"]
rows = 9
cols = 18
print(data.wordsTyping(sentence, rows, cols))
# sentence = ["a", "bcd", "e"]
# rows = 3
# cols = 6
# print(data.wordsTyping(sentence, rows, cols))
# sentence = ["a"]
# rows = 3
# cols = 6
# print(data.wordsTyping(sentence, rows, cols))
# sentence = ["a"]
# rows = 10000
# cols = 10000
# print(data.wordsTyping(sentence, rows, cols))